SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Triangulation (computer vision)</title>

</head>

Triangulation (computer vision)

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">For broader coverage of this topic, see <a href="Computer_stereo_vision" title="Computer stereo vision">Computer stereo vision</a>.</div>

<div role="note" class="hatnote navigation-not-searchable">For other uses, see <a href="Triangulation_(disambiguation)" class="mw-disambig" title="Triangulation (disambiguation)">Triangulation (disambiguation)</a>.</div>

In <a href="Computer_vision" title="Computer vision">computer vision</a>, triangulation refers to the process of determining a point in 3D space given its projections onto two, or more, images. In order to solve this problem it is necessary to know the parameters of the camera projection function from 3D to 2D for the cameras involved, in the simplest case represented by the <a href="Camera_matrix" title="Camera matrix">camera matrices</a>. Triangulation is sometimes also referred to as reconstruction or intersection.

The triangulation problem is in principle trivial. Since each point in an image corresponds to a line in 3D space, all points on the line in 3D are projected to the point in the image. If a pair of <a href="Correspondence_problem" title="Correspondence problem">corresponding points</a> in two, or more images, can be found it must be the case that they are the projection of a common 3D point x. The set of lines generated by the image points must intersect at x (3D point) and the algebraic formulation of the coordinates of x (3D point) can be computed in a variety of ways, as is presented below.

In practice, however, the coordinates of image points cannot be measured with arbitrary accuracy. Instead, various types of noise, such as geometric noise from lens distortion or interest point detection error, lead to inaccuracies in the measured image coordinates. As a consequence, the lines generated by the corresponding image points do not always intersect in 3D space. The problem, then, is to find a 3D point which optimally fits the measured image points. In the literature there are multiple proposals for how to define optimality and how to find the optimal 3D point. Since they are based on different optimality criteria, the various methods produce different estimates of the 3D point x when noise is involved.

<div class="mw-heading mw-heading2"><h2 id="Introduction">Introduction</h2></div>

In the following, it is assumed that triangulation is made on corresponding image points from two views generated by <a href="Pinhole_camera_model" title="Pinhole camera model">pinhole cameras</a>.

The image to the left illustrates the <a href="Epipolar_geometry" title="Epipolar geometry">epipolar geometry</a> of a pair of stereo cameras of <a href="Pinhole_camera_model" title="Pinhole camera model">pinhole model</a>. A point x (3D point) in 3D space is projected onto the respective image plane along a line (green) which goes through the camera's <a href="Focus_(optics)" title="Focus (optics)">focal point</a>, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {O} _{1}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {O} _{1}}</annotation>

</semantics>

</math><img src="./3fea6e9d73f5b8bd4a6afdd928bc623d32deb7e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.062ex; height:2.509ex;" alt="{\displaystyle \mathbf {O} _{1}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {O} _{2}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {O} _{2}}</annotation>

</semantics>

</math><img src="./85659164b901e2b5855f0ae69125ad273e299a83.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.062ex; height:2.509ex;" alt="{\displaystyle \mathbf {O} _{2}}" loading="lazy">, resulting in the two corresponding image points <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {y} _{1}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} _{1}}</annotation>

</semantics>

</math><img src="./d26a1beb48d95f9598bd2144deff52d2b6c75856.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.465ex; height:2.176ex;" alt="{\displaystyle \mathbf {y} _{1}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {y} _{2}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} _{2}}</annotation>

</semantics>

</math><img src="./287f17ca3eb8f472b504a4fa4db4b94a70449794.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.465ex; height:2.176ex;" alt="{\displaystyle \mathbf {y} _{2}}" loading="lazy">. If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {y} _{1}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} _{1}}</annotation>

</semantics>

</math><img src="./d26a1beb48d95f9598bd2144deff52d2b6c75856.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.465ex; height:2.176ex;" alt="{\displaystyle \mathbf {y} _{1}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {y} _{2}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} _{2}}</annotation>

</semantics>

</math><img src="./287f17ca3eb8f472b504a4fa4db4b94a70449794.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.465ex; height:2.176ex;" alt="{\displaystyle \mathbf {y} _{2}}" loading="lazy"> are given and the geometry of the two cameras are known, the two projection lines (green lines) can be determined and it must be the case that they intersect at point x (3D point). Using basic <a href="Linear_algebra" title="Linear algebra">linear algebra</a> that intersection point can be determined in a straightforward way.

The image to the right shows the real case. The position of the image points <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {y} _{1}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} _{1}}</annotation>

</semantics>

</math><img src="./d26a1beb48d95f9598bd2144deff52d2b6c75856.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.465ex; height:2.176ex;" alt="{\displaystyle \mathbf {y} _{1}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {y} _{2}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} _{2}}</annotation>

</semantics>

</math><img src="./287f17ca3eb8f472b504a4fa4db4b94a70449794.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.465ex; height:2.176ex;" alt="{\displaystyle \mathbf {y} _{2}}" loading="lazy"> cannot be measured exactly. The reason is a combination of factors such as

<ul><li>Geometric distortion, for example <a href="Distortion_(optics)" title="Distortion (optics)">lens distortion</a>, which means that the 3D to 2D mapping of the camera deviates from the <a href="Pinhole_camera_model" title="Pinhole camera model">pinhole camera model</a>. To some extent these errors can be compensated for, leaving a residual geometric error.</li>

<li>A single ray of light from x (3D point) is dispersed in the lens system of the cameras according to a <a href="Point_spread_function" title="Point spread function">point spread function</a>. The recovery of the corresponding image point from measurements of the dispersed intensity function in the images gives errors.</li>

<li>In a digital camera, the image intensity function is only measured in discrete sensor elements. Inexact interpolation of the discrete intensity function have to be used to recover the true one.</li>

<li>The image points y1' and y2' used for triangulation are often found using various types of feature extractors, for example of corners or interest points in general. There is an inherent localization error for any type of feature extraction based on <a href="Neighborhood_operation" title="Neighborhood operation">neighborhood operations</a>.</li></ul>

As a consequence, the measured image points are <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {y} '_{1}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} '_{1}}</annotation>

</semantics>

</math><img src="./61f2d2efda4fb8af18596b704e4022e23c02042a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.465ex; height:2.843ex;" alt="{\displaystyle \mathbf {y} '_{1}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {y} '_{2}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} '_{2}}</annotation>

</semantics>

</math><img src="./0951c7ff99e53d2890d601fa64b6eba1b0abe8dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.465ex; height:2.843ex;" alt="{\displaystyle \mathbf {y} '_{2}}" loading="lazy"> instead of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {y} _{1}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} _{1}}</annotation>

</semantics>

</math><img src="./d26a1beb48d95f9598bd2144deff52d2b6c75856.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.465ex; height:2.176ex;" alt="{\displaystyle \mathbf {y} _{1}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {y} _{2}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} _{2}}</annotation>

</semantics>

</math><img src="./287f17ca3eb8f472b504a4fa4db4b94a70449794.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.465ex; height:2.176ex;" alt="{\displaystyle \mathbf {y} _{2}}" loading="lazy">. However, their projection lines (blue) do not have to intersect in 3D space or come close to x. In fact, these lines intersect if and only if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {y} '_{1}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} '_{1}}</annotation>

</semantics>

</math><img src="./61f2d2efda4fb8af18596b704e4022e23c02042a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.465ex; height:2.843ex;" alt="{\displaystyle \mathbf {y} '_{1}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {y} '_{2}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} '_{2}}</annotation>

</semantics>

</math><img src="./0951c7ff99e53d2890d601fa64b6eba1b0abe8dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.465ex; height:2.843ex;" alt="{\displaystyle \mathbf {y} '_{2}}" loading="lazy"> satisfy the <a href="Epipolar_constraint" class="mw-redirect" title="Epipolar constraint">epipolar constraint</a> defined by the <a href="Fundamental_matrix_(computer_vision)" title="Fundamental matrix (computer vision)">fundamental matrix</a>. Given the measurement noise in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {y} '_{1}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} '_{1}}</annotation>

</semantics>

</math><img src="./61f2d2efda4fb8af18596b704e4022e23c02042a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.465ex; height:2.843ex;" alt="{\displaystyle \mathbf {y} '_{1}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {y} '_{2}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} '_{2}}</annotation>

</semantics>

</math><img src="./0951c7ff99e53d2890d601fa64b6eba1b0abe8dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.465ex; height:2.843ex;" alt="{\displaystyle \mathbf {y} '_{2}}" loading="lazy"> it is rather likely that the epipolar constraint is not satisfied and the projection lines do not intersect.

This observation leads to the problem which is solved in triangulation. Which 3D point xest is the best estimate of x given <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {y} '_{1}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} '_{1}}</annotation>

</semantics>

</math><img src="./61f2d2efda4fb8af18596b704e4022e23c02042a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.465ex; height:2.843ex;" alt="{\displaystyle \mathbf {y} '_{1}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {y} '_{2}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} '_{2}}</annotation>

</semantics>

</math><img src="./0951c7ff99e53d2890d601fa64b6eba1b0abe8dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.465ex; height:2.843ex;" alt="{\displaystyle \mathbf {y} '_{2}}" loading="lazy"> and the geometry of the cameras? The answer is often found by defining an error measure which depends on xest and then minimizing this error. In the following sections, some of the various methods for computing xest presented in the literature are briefly described.

All triangulation methods produce xest = x in the case that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {y} _{1}=\mathbf {y} '_{1}}">

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} _{1}=\mathbf {y} '_{1}}</annotation>

</semantics>

</math><img src="./25e67c0ead512205e0d17468a0a0b0b63200ae2a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.029ex; height:2.843ex;" alt="{\displaystyle \mathbf {y} _{1}=\mathbf {y} '_{1}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {y} _{2}=\mathbf {y} '_{2}}">

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} _{2}=\mathbf {y} '_{2}}</annotation>

</semantics>

</math><img src="./c3881a5e67281a2d74587c66c8abef6a7ba92c87.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.029ex; height:2.843ex;" alt="{\displaystyle \mathbf {y} _{2}=\mathbf {y} '_{2}}" loading="lazy">, that is, when the epipolar constraint is satisfied (except for singular points, see below). It is what happens when the constraint is not satisfied which differs between the methods.

<div class="mw-heading mw-heading2"><h2 id="Properties">Properties</h2></div>

A triangulation method can be described in terms of a function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \tau \,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \tau \,}</annotation>

</semantics>

</math><img src="./8661cd2a09f95bb46a58ad86eebc9c7d81a31bea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.589ex; height:1.676ex;" alt="{\displaystyle \tau \,}" loading="lazy"> such that

</mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {x} \sim \tau (\mathbf {y} '_{1},\mathbf {y} '_{2},\mathbf {C} _{1},\mathbf {C} _{2})}</annotation>

</semantics>

</math><img src="./28e0bedb5e5e16e53ea72ffc63a0f0a97ea6b0d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:21.524ex; height:3.009ex;" alt="{\displaystyle \mathbf {x} \sim \tau (\mathbf {y} '_{1},\mathbf {y} '_{2},\mathbf {C} _{1},\mathbf {C} _{2})}" loading="lazy"></dd></dl>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {y} '_{1},\mathbf {y} '_{2}}">

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} '_{1},\mathbf {y} '_{2}}</annotation>

</semantics>

</math><img src="./db827a3891ac73b3825d0e85a1042e7711bdcefb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:5.964ex; height:2.843ex;" alt="{\displaystyle \mathbf {y} '_{1},\mathbf {y} '_{2}}" loading="lazy"> are the homogeneous coordinates of the detected image points and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {C} _{1},\mathbf {C} _{2}}">

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {C} _{1},\mathbf {C} _{2}}</annotation>

</semantics>

</math><img src="./4be362e8a89e2dbb9a47cc31a45e95cf84cc07f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.005ex; height:2.509ex;" alt="{\displaystyle \mathbf {C} _{1},\mathbf {C} _{2}}" loading="lazy"> are the camera matrices. x (3D point) is the homogeneous representation of the resulting 3D point. The <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sim \,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sim \,}</annotation>

</semantics>

</math><img src="./ce5528a8c86c5b0121f9448aa9a117429f5b9c88.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:2.195ex; height:1.343ex;" alt="{\displaystyle \sim \,}" loading="lazy"> sign implies that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \tau \,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \tau \,}</annotation>

</semantics>

</math><img src="./8661cd2a09f95bb46a58ad86eebc9c7d81a31bea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.589ex; height:1.676ex;" alt="{\displaystyle \tau \,}" loading="lazy"> is only required to produce a vector which is equal to x up to a multiplication by a non-zero scalar since homogeneous vectors are involved.

Before looking at the specific methods, that is, specific functions <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \tau \,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \tau \,}</annotation>

</semantics>

</math><img src="./8661cd2a09f95bb46a58ad86eebc9c7d81a31bea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.589ex; height:1.676ex;" alt="{\displaystyle \tau \,}" loading="lazy">, there are some general concepts related to the methods that need to be explained. Which triangulation method is chosen for a particular problem depends to some extent on these characteristics.

<div class="mw-heading mw-heading3"><h3 id="Singularities">Singularities</h3></div>

Some of the methods fail to correctly compute an estimate of x (3D point) if it lies in a certain subset of the 3D space, corresponding to some combination of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {y} '_{1},\mathbf {y} '_{2},\mathbf {C} _{1},\mathbf {C} _{2}}">

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} '_{1},\mathbf {y} '_{2},\mathbf {C} _{1},\mathbf {C} _{2}}</annotation>

</semantics>

</math><img src="./b0e838676a41a4795f8b65a05d8efe73668845aa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:14.003ex; height:2.843ex;" alt="{\displaystyle \mathbf {y} '_{1},\mathbf {y} '_{2},\mathbf {C} _{1},\mathbf {C} _{2}}" loading="lazy">. A point in this subset is then a singularity of the triangulation method. The reason for the failure can be that some equation system to be solved is under-determined or that the projective representation of xest becomes the zero vector for the singular points.

<div class="mw-heading mw-heading3"><h3 id="Invariance">Invariance</h3></div>

In some applications, it is desirable that the triangulation is independent of the coordinate system used to represent 3D points; if the triangulation problem is formulated in one coordinate system and then transformed into another the resulting estimate xest should transform in the same way. This property is commonly referred to as invariance. Not every triangulation method assures invariance, at least not for general types of coordinate transformations.

For a homogeneous representation of 3D coordinates, the most general transformation is a projective transformation, represented by a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 4\times 4}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 4\times 4}</annotation>

</semantics>

</math><img src="./89eb2e0f4ddfe5f30c8016a0f2aa1fb5ecedfe20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.165ex; height:2.176ex;" alt="{\displaystyle 4\times 4}" loading="lazy"> matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {T} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {T} }</annotation>

</semantics>

</math><img src="./9593e3b995a1b57c078873a5ea186c7012e1a5ee.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.859ex; height:2.176ex;" alt="{\displaystyle \mathbf {T} }" loading="lazy">. If the homogeneous coordinates are transformed according to

<mover>

</mover>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {\bar {x}} \sim \mathbf {T} \,\mathbf {x} }</annotation>

</semantics>

</math><img src="./7fab03aa34a4845c8fd06b0ee935cb329e8ee039.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.167ex; height:2.176ex;" alt="{\displaystyle \mathbf {\bar {x}} \sim \mathbf {T} \,\mathbf {x} }" loading="lazy"></dd></dl>

then the camera matrices must transform as (Ck)

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {\bar {C}} _{k}\sim \mathbf {C} _{k}\,\mathbf {T} ^{-1}}</annotation>

</semantics>

</math><img src="./8e1239ec2a8a384b447a43ac1559b708a45390b9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.717ex; height:3.009ex;" alt="{\displaystyle \mathbf {\bar {C}} _{k}\sim \mathbf {C} _{k}\,\mathbf {T} ^{-1}}" loading="lazy"></dd></dl>

to produce the same homogeneous image coordinates (yk)

<msub>

</mrow>

</mrow>

</msub>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<mover>

</mover>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} _{k}\sim \mathbf {\bar {C}} _{k}\,\mathbf {\bar {x}} =\mathbf {C} _{k}\,\mathbf {x} }</annotation>

</semantics>

</math><img src="./59eb73f56cb6ce6b02fc4da38e9161257eee9635.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.333ex; height:3.176ex;" alt="{\displaystyle \mathbf {y} _{k}\sim \mathbf {\bar {C}} _{k}\,\mathbf {\bar {x}} =\mathbf {C} _{k}\,\mathbf {x} }" loading="lazy"></dd></dl>

If the triangulation function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \tau }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \tau }</annotation>

</semantics>

</math><img src="./38a7dcde9730ef0853809fefc18d88771f95206c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.202ex; height:1.676ex;" alt="{\displaystyle \tau }" loading="lazy"> is invariant to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {T} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {T} }</annotation>

</semantics>

</math><img src="./9593e3b995a1b57c078873a5ea186c7012e1a5ee.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.859ex; height:2.176ex;" alt="{\displaystyle \mathbf {T} }" loading="lazy"> then the following relation must be valid

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {\bar {x}} _{\rm {est}}\sim \mathbf {T} \,\mathbf {x} _{\rm {est}}}</annotation>

</semantics>

</math><img src="./e0a270ae879214a3a1e4efcf593961a76bf06e77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.666ex; height:2.509ex;" alt="{\displaystyle \mathbf {\bar {x}} _{\rm {est}}\sim \mathbf {T} \,\mathbf {x} _{\rm {est}}}" loading="lazy"></dd></dl>

from which follows that

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</mrow>

</msub>

<msup>

</mrow>

</mrow>

</msup>

<msub>

</mrow>

</mrow>

</msub>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \tau (\mathbf {y} '_{1},\mathbf {y} '_{2},\mathbf {C} _{1},\mathbf {C} _{2})\sim \mathbf {T} ^{-1}\,\tau (\mathbf {y} '_{1},\mathbf {y} '_{2},\mathbf {C} _{1}\,\mathbf {T} ^{-1},\mathbf {C} _{2}\,\mathbf {T} ^{-1}),}</annotation>

</semantics>

</math><img src="./d1d19ec53fd688a8bd228e2925ee73da500b0f81.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:51.511ex; height:3.343ex;" alt="{\displaystyle \tau (\mathbf {y} '_{1},\mathbf {y} '_{2},\mathbf {C} _{1},\mathbf {C} _{2})\sim \mathbf {T} ^{-1}\,\tau (\mathbf {y} '_{1},\mathbf {y} '_{2},\mathbf {C} _{1}\,\mathbf {T} ^{-1},\mathbf {C} _{2}\,\mathbf {T} ^{-1}),}" loading="lazy">   for all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {y} '_{1},\mathbf {y} '_{2}}">

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} '_{1},\mathbf {y} '_{2}}</annotation>

</semantics>

</math><img src="./db827a3891ac73b3825d0e85a1042e7711bdcefb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:5.964ex; height:2.843ex;" alt="{\displaystyle \mathbf {y} '_{1},\mathbf {y} '_{2}}" loading="lazy"></dd></dl>

For each triangulation method, it can be determined if this last relation is valid. If it is, it may be satisfied only for a subset of the projective transformations, for example, rigid or affine transformations.

<div class="mw-heading mw-heading3"><h3 id="Computational_complexity">Computational complexity</h3></div>

The function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \tau }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \tau }</annotation>

</semantics>

</math><img src="./38a7dcde9730ef0853809fefc18d88771f95206c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.202ex; height:1.676ex;" alt="{\displaystyle \tau }" loading="lazy"> is only an abstract representation of a computation which, in practice, may be relatively complex. Some methods result in a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \tau }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \tau }</annotation>

</semantics>

</math><img src="./38a7dcde9730ef0853809fefc18d88771f95206c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.202ex; height:1.676ex;" alt="{\displaystyle \tau }" loading="lazy"> which is a closed-form continuous function while others need to be decomposed into a series of computational steps involving, for example, <a href="Singular_value_decomposition" title="Singular value decomposition">SVD</a> or finding the roots of a polynomial. Yet another class of methods results in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \tau }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \tau }</annotation>

</semantics>

</math><img src="./38a7dcde9730ef0853809fefc18d88771f95206c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.202ex; height:1.676ex;" alt="{\displaystyle \tau }" loading="lazy"> which must rely on iterative estimation of some parameters. This means that both the computation time and the complexity of the operations involved may vary between the different methods.

<div class="mw-heading mw-heading2"><h2 id="Methods">Methods</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Mid-point_method">Mid-point method</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Further information: <a href="Skew_lines#Nearest_points" title="Skew lines">Skew lines § Nearest points</a></div>

Each of the two image points <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {y} '_{1}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} '_{1}}</annotation>

</semantics>

</math><img src="./61f2d2efda4fb8af18596b704e4022e23c02042a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.465ex; height:2.843ex;" alt="{\displaystyle \mathbf {y} '_{1}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {y} '_{2}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} '_{2}}</annotation>

</semantics>

</math><img src="./0951c7ff99e53d2890d601fa64b6eba1b0abe8dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.465ex; height:2.843ex;" alt="{\displaystyle \mathbf {y} '_{2}}" loading="lazy"> has a corresponding projection line (blue in the right image above), here denoted as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {L} '_{1}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {L} '_{1}}</annotation>

</semantics>

</math><img src="./5aa7173eb26790c21dff54bd9096e5efbf5d87a4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.663ex; height:3.009ex;" alt="{\displaystyle \mathbf {L} '_{1}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {L} '_{2}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {L} '_{2}}</annotation>

</semantics>

</math><img src="./353b9bb1f0c774b438cc8542007daaff2302b79e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.663ex; height:3.009ex;" alt="{\displaystyle \mathbf {L} '_{2}}" loading="lazy">, which can be determined given the camera matrices <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {C} _{1},\mathbf {C} _{2}}">

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {C} _{1},\mathbf {C} _{2}}</annotation>

</semantics>

</math><img src="./4be362e8a89e2dbb9a47cc31a45e95cf84cc07f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.005ex; height:2.509ex;" alt="{\displaystyle \mathbf {C} _{1},\mathbf {C} _{2}}" loading="lazy">. Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d\,}</annotation>

</semantics>

</math><img src="./0f203b686a923982358b9274fb508753ac31b996.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.603ex; height:2.176ex;" alt="{\displaystyle d\,}" loading="lazy"> be a distance function between a (3D line) L and a x (3D point) such that

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d(\mathbf {L} ,\mathbf {x} )}</annotation>

</semantics>

</math><img src="./016069150232e117050c40277bc8b129409cf1c4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.078ex; height:2.843ex;" alt="{\displaystyle d(\mathbf {L} ,\mathbf {x} )}" loading="lazy"> is the Euclidean distance between <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {L} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {L} }</annotation>

</semantics>

</math><img src="./6f5f750865376a1a4ae2b15a00b4ff9c75a66630.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.608ex; height:2.176ex;" alt="{\displaystyle \mathbf {L} }" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {x} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {x} }</annotation>

</semantics>

</math><img src="./32adf004df5eb0a8c7fd8c0b6b7405183c5a5ef2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.411ex; height:1.676ex;" alt="{\displaystyle \mathbf {x} }" loading="lazy">.

The midpoint method finds the point xest which minimizes

</mrow>

</mrow>

</msubsup>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msubsup>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d(\mathbf {L} '_{1},\mathbf {x} )^{2}+d(\mathbf {L} '_{2},\mathbf {x} )^{2}}</annotation>

</semantics>

</math><img src="./065eca4d8285dfe9ebd39415eb44d39bdb81e608.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.214ex; height:3.176ex;" alt="{\displaystyle d(\mathbf {L} '_{1},\mathbf {x} )^{2}+d(\mathbf {L} '_{2},\mathbf {x} )^{2}}" loading="lazy"></dd></dl>

It turns out that xest lies exactly at the middle of the shortest line segment which joins the two projection lines.

<div class="mw-heading mw-heading3"><h3 id="Direct_linear_transformation">Direct linear transformation</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Direct_linear_transformation" title="Direct linear transformation">Direct linear transformation</a></div>

<div class="mw-heading mw-heading3"><h3 id="Via_the_essential_matrix">Via the essential matrix</h3></div>

The problem to be solved there is how to compute <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x_{1},x_{2},x_{3})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x_{1},x_{2},x_{3})}</annotation>

</semantics>

</math><img src="./c299961b19740135135d0ef0289b16b6095048d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.029ex; height:2.843ex;" alt="{\displaystyle (x_{1},x_{2},x_{3})}" loading="lazy"> given corresponding normalized image coordinates <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (y_{1},y_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (y_{1},y_{2})}</annotation>

</semantics>

</math><img src="./e4f050945a3f09325c2d582048d8343119364a8c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.23ex; height:2.843ex;" alt="{\displaystyle (y_{1},y_{2})}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (y'_{1},y'_{2})}">

</mrow>

</msubsup>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (y'_{1},y'_{2})}</annotation>

</semantics>

</math><img src="./4965a635f305ad9a37a194e2393410050a82510b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:7.23ex; height:3.009ex;" alt="{\displaystyle (y'_{1},y'_{2})}" loading="lazy">. If the <a href="Essential_matrix" title="Essential matrix">essential matrix</a> is known and the corresponding rotation and translation transformations have been determined, this algorithm (described in Longuet-Higgins' paper) provides a solution.

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {r} _{k}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {r} _{k}}</annotation>

</semantics>

</math><img src="./01da6ca6fcfe0ac44e859a2bad84c3d90846f195.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.191ex; height:2.009ex;" alt="{\displaystyle \mathbf {r} _{k}}" loading="lazy"> denote row k of the rotation matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {R} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {R} }</annotation>

</semantics>

</math><img src="./5de85fcc2a00d8ba14aae84aeef812d7fef4b3d5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.003ex; height:2.176ex;" alt="{\displaystyle \mathbf {R} }" loading="lazy">:

</mrow>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {R} ={\begin{pmatrix}-\mathbf {r} _{1}-\\-\mathbf {r} _{2}-\\-\mathbf {r} _{3}-\end{pmatrix}}}</annotation>

</semantics>

</math><img src="./7eef9e2743c4cc30eea3d90c3d1f7c3384e822cb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.005ex; width:15.693ex; height:9.176ex;" alt="{\displaystyle \mathbf {R} ={\begin{pmatrix}-\mathbf {r} _{1}-\\-\mathbf {r} _{2}-\\-\mathbf {r} _{3}-\end{pmatrix}}}" loading="lazy"></dd></dl>

Combining the above relations between 3D coordinates in the two coordinate systems and the mapping between 3D and 2D points described earlier gives

</mrow>

</msubsup>

<mfrac>

</mrow>

</msubsup>

</mrow>

</msubsup>

</mfrac>

</mrow>

<mfrac>

<mrow>

<msub>

</mrow>

</mrow>

</msub>

<mover>

</mrow>

</mover>

</mrow>

</mrow>

</mrow>

<mrow>

<msub>

</mrow>

</mrow>

</msub>

<mover>

</mrow>

</mover>

</mrow>

</mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y'_{1}={\frac {x'_{1}}{x'_{3}}}={\frac {\mathbf {r} _{1}\cdot ({\tilde {\mathbf {x} }}-\mathbf {t} )}{\mathbf {r} _{3}\cdot ({\tilde {\mathbf {x} }}-\mathbf {t} )}}={\frac {\mathbf {r} _{1}\cdot (\mathbf {y} -\mathbf {t} /x_{3})}{\mathbf {r} _{3}\cdot (\mathbf {y} -\mathbf {t} /x_{3})}}}</annotation>

</semantics>

</math><img src="./3398221f995ca30cc1fa744fef425ce37d255769.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:41.798ex; height:6.509ex;" alt="{\displaystyle y'_{1}={\frac {x'_{1}}{x'_{3}}}={\frac {\mathbf {r} _{1}\cdot ({\tilde {\mathbf {x} }}-\mathbf {t} )}{\mathbf {r} _{3}\cdot ({\tilde {\mathbf {x} }}-\mathbf {t} )}}={\frac {\mathbf {r} _{1}\cdot (\mathbf {y} -\mathbf {t} /x_{3})}{\mathbf {r} _{3}\cdot (\mathbf {y} -\mathbf {t} /x_{3})}}}" loading="lazy"></dd></dl>

or

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</msubsup>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

<mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</msubsup>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{3}={\frac {(\mathbf {r} _{1}-y'_{1}\,\mathbf {r} _{3})\cdot \mathbf {t} }{(\mathbf {r} _{1}-y'_{1}\,\mathbf {r} _{3})\cdot \mathbf {y} }}}</annotation>

</semantics>

</math><img src="./c16aa7973e504627d11b687955b98c1fe60b9ecf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.838ex; width:20.951ex; height:6.676ex;" alt="{\displaystyle x_{3}={\frac {(\mathbf {r} _{1}-y'_{1}\,\mathbf {r} _{3})\cdot \mathbf {t} }{(\mathbf {r} _{1}-y'_{1}\,\mathbf {r} _{3})\cdot \mathbf {y} }}}" loading="lazy"></dd></dl>

Once <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{3}}</annotation>

</semantics>

</math><img src="./766d09a498699be10e276ad49145c921f8cbe335.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.384ex; height:2.009ex;" alt="{\displaystyle x_{3}}" loading="lazy"> is determined, the other two coordinates can be computed as

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

<msub>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}=x_{3}{\begin{pmatrix}y_{1}\\y_{2}\end{pmatrix}}}</annotation>

</semantics>

</math><img src="./9fb7b18cbc8e7db18a8362e377196051b14c4c2f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:18.405ex; height:6.176ex;" alt="{\displaystyle {\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}=x_{3}{\begin{pmatrix}y_{1}\\y_{2}\end{pmatrix}}}" loading="lazy"></dd></dl>

The above derivation is not unique. It is also possible to start with an expression for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y'_{2}}">

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y'_{2}}</annotation>

</semantics>

</math><img src="./5df7ed6173a4495dafd4f37bf26808f4a4667785.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.193ex; height:2.843ex;" alt="{\displaystyle y'_{2}}" loading="lazy"> and derive an expression for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{3}}</annotation>

</semantics>

</math><img src="./766d09a498699be10e276ad49145c921f8cbe335.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.384ex; height:2.009ex;" alt="{\displaystyle x_{3}}" loading="lazy"> according to

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</msubsup>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

<mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</msubsup>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{3}={\frac {(\mathbf {r} _{2}-y'_{2}\,\mathbf {r} _{3})\cdot \mathbf {t} }{(\mathbf {r} _{2}-y'_{2}\,\mathbf {r} _{3})\cdot \mathbf {y} }}}</annotation>

</semantics>

</math><img src="./bc52f906caa51709990c1735fc5aad16e2879d4e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.838ex; width:20.951ex; height:6.676ex;" alt="{\displaystyle x_{3}={\frac {(\mathbf {r} _{2}-y'_{2}\,\mathbf {r} _{3})\cdot \mathbf {t} }{(\mathbf {r} _{2}-y'_{2}\,\mathbf {r} _{3})\cdot \mathbf {y} }}}" loading="lazy"></dd></dl>

In the ideal case, when the camera maps the 3D points according to a perfect pinhole camera and the resulting 2D points can be detected without any noise, the two expressions for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{3}}</annotation>

</semantics>

</math><img src="./766d09a498699be10e276ad49145c921f8cbe335.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.384ex; height:2.009ex;" alt="{\displaystyle x_{3}}" loading="lazy"> are equal. In practice, however, they are not and it may be advantageous to combine the two estimates of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{3}}</annotation>

</semantics>

</math><img src="./766d09a498699be10e276ad49145c921f8cbe335.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.384ex; height:2.009ex;" alt="{\displaystyle x_{3}}" loading="lazy">, for example, in terms of some sort of average.

There are also other types of extensions of the above computations which are possible. They started with an expression of the primed image coordinates and derived 3D coordinates in the unprimed system. It is also possible to start with unprimed image coordinates and obtain primed 3D coordinates, which finally can be transformed into unprimed 3D coordinates. Again, in the ideal case the result should be equal to the above expressions, but in practice they may deviate.

A final remark relates to the fact that if the essential matrix is determined from corresponding image coordinate, which often is the case when 3D points are determined in this way, the translation vector <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {t} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {t} }</annotation>

</semantics>

</math><img src="./16ff63cc74a931900e79b3caacbae3fa8cc66845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.039ex; height:2.009ex;" alt="{\displaystyle \mathbf {t} }" loading="lazy"> is known only up to an unknown positive scaling. As a consequence, the reconstructed 3D points, too, are undetermined with respect to a positive scaling.

<ul><li><a href="3D_reconstruction_from_multiple_images" title="3D reconstruction from multiple images">3D reconstruction from multiple images</a></li>

<li><a href="Bundle_adjustment" title="Bundle adjustment">Bundle adjustment</a></li>

<li><a href="Line%E2%80%93line_intersection" title="Line–line intersection">Line–line intersection</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFRichard_Hartley_and_Andrew_Zisserman2003" class="citation book cs1">Richard Hartley and Andrew Zisserman (2003). Multiple View Geometry in computer vision. Cambridge University Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-54051-3</bdi>.</cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://www.mathworks.com/matlabcentral/fileexchange/67383-stereo-triangulation">Two view</a> and <a rel="nofollow" class="external text" href="https://www.mathworks.com/matlabcentral/fileexchange/78955-multi-view-triangulation">multi-view</a> triangulation in Matlab</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-08-19" href="https://en.wikipedia.org/wiki/?title=Triangulation_(computer_vision)&oldid=1241190657">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>